package com.alg;

import com.immomo.mcf.util.StringUtils;

import java.util.*;

/**
 * @author: sun.hongliang
 * @create: 2019/12/26 15:22
 */
public class ArrayTest {
    public static void main(String[] args) {

        String b = "43535," +
                "26223," +
                "56452," +
                "22156," +
                "62436," +
                "53476," +
                "51452," +
                "33551," +
                "49200," +
                "26390," +
                "59992," +
                "20817," +
                "13165," +
                "47986," +
                "28547," +
                "21910," +
                "14452," +
                "55729," +
                "18877," +
                "15537," +
                "16372," +
                "61331," +
                "19563," +
                "41078," +
                "16726," +
                "32714," +
                "9400," +
                "79771," +
                "81413," +
                "89518," +
                "31336," +
                "15457," +
                "32376," +
                "29859," +
                "42226," +
                "72493," +
                "66614," +
                "65057," +
                "47143," +
                "85827," +
                "72269," +
                "59724," +
                "61521," +
                "91733," +
                "82538," +
                "85376," +
                "55418," +
                "67238," +
                "87498," +
                "84170," +
                "73673," +
                "12726," +
                "81615," +
                "73938," +
                "55763," +
                "81628," +
                "80854," +
                "88799," +
                "70114," +
                "62432," +
                "41951," +
                "73972," +
                "27892," +
                "88833," +
                "90634," +
                "89351," +
                "90384," +
                "78863," +
                "35345," +
                "92741," +
                "89150," +
                "87896," +
                "85300," +
                "85024," +
                "72503," +
                "62005," +
                "91768," +
                "91764," +
                "89469," +
                "83560," +
                "79471," +
                "72338," +
                "72085," +
                "16765," +
                "87227," +
                "86686," +
                "84907," +
                "83133," +
                "76981," +
                "9407," +
                "86469," +
                "90108," +
                "82683," +
                "79324," +
                "71926," +
                "60664," +
                "41798," +
                "17209," +
                "12824," +
                "72796," +
                "17773," +
                "70768," +
                "33407," +
                "25510," +
                "15749," +
                "72128," +
                "62659," +
                "31439," +
                "22966," +
                "20680," +
                "12998," +
                "67111," +
                "31625," +
                "30685," +
                "18936," +
                "15535," +
                "86198," +
                "85161," +
                "59690," +
                "29889," +
                "28198," +
                "73070," +
                "38271," +
                "30538," +
                "83233," +
                "70203," +
                "67890," +
                "63520," +
                "45803," +
                "44935," +
                "38992," +
                "14603," +
                "82783," +
                "78220," +
                "72344," +
                "54133," +
                "49780," +
                "35556," +
                "22857," +
                "16743," +
                "16601," +
                "10980," +
                "8079," +
                "85053," +
                "73060," +
                "59790," +
                "59515," +
                "33132," +
                "77006";
        String[] split = StringUtils.split(b, ",");
        StringBuilder sb = new StringBuilder();

        for (String s : split) {
            sb.append(s);
            sb.append(",");
        }
        System.out.println(sb.toString());
    }

    public String compressString(String S) {
        int len = S.length();
        if (len <= 1) return S;
        char[] chars = S.toCharArray();
        StringBuilder sb = new StringBuilder();
        sb.append(chars[0]);
        int count = 1;
        for (int i = 1; i < len; i++) {
            if (chars[i] == chars[i - 1]) {
                count++;
            } else {
                sb.append(count);
                sb.append(chars[i]);
                count = 1;
            }
        }
        sb.append(count);
        return sb.toString().length() < S.length() ? sb.toString() : S;
    }

    public boolean CheckPermutation(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
        Map<Character, Integer> map = new HashMap<>();
        char[] chars = s1.toCharArray();
        for (char t : chars) {
            map.put(t, map.getOrDefault(t, 0) + 1);
        }

        char[] chars2 = s2.toCharArray();
        for (char c : chars2) {
            if (!map.containsKey(c)) {
                return false;
            }
            Integer count = map.get(c);
            count = count - 1;
            map.put(c, count);
            if (count < 0) {
                return false;
            }
        }
        return true;
    }

    public boolean isUnique(String astr) {
        long low64 = 0;
        long hig64 = 0;
        char[] chars = astr.toCharArray();
        for (char c : chars) {
            if (c >= 64) {
                long index = 1L << (c - 64);
                if ((index & hig64) != 0) {
                    return false;
                }
                hig64 |= index;
            } else {
                long index = 1L << c;
                if ((index & low64) != 0) {
                    return false;
                }
                low64 |= index;
            }
        }
        return true;
    }

    public static int[][] generateMatrix(int n) {
        int[][] nums = new int[n][n];
        int num = 1;
        int start = 0;
        int end = n - 1;
        while (start <= end) {
            for (int j = start; j <= end; j++) {
                nums[start][j] = num++;
            }
            for (int i = start + 1; i <= end; i++) {
                nums[i][end] = num++;
            }
            for (int j = end - 1; j >= start; j--) {
                nums[end][j] = num++;
            }
            for (int i = end - 1; i >= start + 1; i--) {
                nums[i][start] = num++;
            }
            start++;
            end--;
        }
        return nums;
    }

    public static int removeDuplicates(int[] nums) {
        int len = nums.length;
        int j = 0;
        for (int i = 0; i < len; i++) {
            if (nums[i] != nums[j]) {
                j++;
                nums[j] = nums[i];
            }
        }
        return j + 1;
    }

    public static int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int len = nums.length;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < len; i++) {
            int start = i + 1;
            int end = len - 1;
            while (start < end) {
                int sum = nums[start] + nums[end] + nums[i];
                if (sum == target) {
                    return 0;
                }
                if (Math.abs(sum - target) < Math.abs(min - target)) {
                    min = sum;
                }
                if (sum > target) {
                    end--;
                } else {
                    start++;
                }
            }
        }
        return min;
    }

    int[] nums;

    public void swap(int a, int b) {
        int tmp = this.nums[a];
        this.nums[a] = this.nums[b];
        this.nums[b] = tmp;
    }


    public int partition(int left, int right, int pivot_index) {
        int pivot = this.nums[pivot_index];
        swap(pivot_index, right);
        int store_index = left;
        for (int i = left; i <= right; i++) {
            if (this.nums[i] < pivot) {
                swap(store_index, i);
                store_index++;
            }
        }
        swap(store_index, right);
        return store_index;
    }

    public int quickselect(int left, int right, int k_smallest) {
        if (left == right)
            return this.nums[left];
        Random random_num = new Random();
        int pivot_index = left + random_num.nextInt(right - left);
        pivot_index = partition(left, right, pivot_index);
        if (k_smallest == pivot_index)
            return this.nums[k_smallest];
        else if (k_smallest < pivot_index)
            return quickselect(left, pivot_index - 1, k_smallest);
        return quickselect(pivot_index + 1, right, k_smallest);
    }

    public int findKthLargest(int[] nums, int k) {
        this.nums = nums;
        int size = nums.length;
        return quickselect(0, size - 1, size - k);
    }


    public static List<Integer> findDisappearedNumbers(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            int index = Math.abs(nums[i]) - 1;
            if (nums[index] > 0) {
                nums[index] = -nums[index];
            }
        }
        List<Integer> list = new LinkedList<>();
        for (int i = 0; i < len; i++) {
            if (nums[i] > 0) {
                list.add(i + 1);
            }
        }
        return list;
    }

    public int removeElement(int[] nums, int val) {
        int len = nums.length;
        int n = 0;
        for (int i = 0; i < len; i++) {
            if (nums[i] != val) {
                nums[n++] = nums[i];
            }
        }
        return n;
    }


    public int searchInsert(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = (l + r + 1) >> 1;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] > target) {
                r = mid - 1;
            } else {
                l = mid;
            }
        }
        return l;
    }

    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int l = 0, r = m * n;
        while (l <= r) {
            int mid = (l + r) >> 1;
            int newM = mid / n;
            int newN = mid % n;
            int temp = matrix[newM][newN];
            if (temp == target) {
                return true;
            }
            if (temp > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return false;
    }

    public static int trap(int[] height) {
        int len = height.length;
        if (len == 0) return 0;
        int[] dp_l = new int[len];

        dp_l[1] = height[0];
        for (int i = 2; i < len; i++) {
            dp_l[i] = Math.max(dp_l[i - 1], height[i - 1]);
        }

        int[] dp_r = new int[len];
        dp_r[len - 2] = height[len - 1];
        for (int i = len - 3; i >= 0; i--) {
            dp_r[i] = Math.max(dp_r[i + 1], height[i + 1]);
        }

        int res = 0;
        for (int i = 0; i < len - 1; i++) {
            int minH = Math.min(dp_l[i], dp_r[i]);
            int h = height[i];
            if (minH > h) {
                res += minH - h;
            }
        }
        return res;
    }

    public static int removeDuplicates2(int[] nums) {
        if (nums.length <= 2) {
            return nums.length;
        }
        int j = 2;
        for (int i = 2; i < nums.length; i++) {
            if (nums[i] != nums[j - 2]) {
                nums[j++] = nums[i];
            }
        }
        return j + 1;
    }

    public int findMin(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (nums[mid] > nums[l]) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return nums[l];
    }

    public int findMin2(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }

        int left = 0, right = nums.length - 1;

        if (nums[right] > nums[0]) {
            return nums[0];
        }

        while (right >= left) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                return nums[mid + 1];
            }
            if (nums[mid - 1] > nums[mid]) {
                return nums[mid];
            }
            if (nums[mid] > nums[0]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }

//    [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

    public static int[] dailyTemperatures(int[] T) {
        int len = T.length;
        if (len == 0) return new int[0];
        if (len == 1) return new int[]{0};
        int[] res = new int[len];
        for (int i = len - 2; i >= 0; i--) {
            for (int j = i + 1; j < len; j += res[j]) {
                if (T[j] > T[i]) {
                    res[i] = j - i;
                    break;
                }
                if (res[j] == 0) {
                    break;
                }
            }
        }
        return res;
    }

    public static int[] dailyTemperatures2(int[] T) {
        int len = T.length;
        if (len == 0) return new int[0];
        if (len == 1) return new int[]{0};
        int[] res = new int[len];
        Stack<Integer> stack = new Stack<>();
        for (int i = len - 1; i >= 0; i--) {
            while (!stack.isEmpty() && T[stack.peek()] <= T[i]) {
                stack.pop();
            }
            res[i] = stack.isEmpty() ? 0 : stack.peek() - i;
            stack.push(i);
        }
        return res;
    }

    public static int countSubstrings(String s) {
        if (s == null || s.length() == 0) return 0;
        int len = s.length();
        int[] dp = new int[len];
        dp[0] = 1;
        char[] chars = s.toCharArray();
        for (int i = 1; i < len; i++) {
            dp[i] = dp[i - 1] + getSubCount(chars, i);
        }
        System.out.println(Arrays.toString(dp));
        return dp[len - 1];
    }

    private static int getSubCount(char[] chars, int i) {
        int res = 0;
        for (int j = 0; j <= i; j++) {
            int start = j, end = i;
            boolean flg = true;
            while (start < end) {
                if (chars[start] != chars[end]) {
                    flg = false;
                    break;
                }
                start++;
                end--;
            }
            if (flg) {
                res++;
            }
        }
        return res;
    }

    public static int leastInterval(char[] tasks, int n) {
        if (tasks.length == 0) return 0;
        if (tasks.length == 1) return 1;
        Map<Character, Integer> tCountMap = new HashMap<>();
        for (Character c : tasks) {
            Integer count = tCountMap.getOrDefault(c, 0);
            tCountMap.put(c, count + 1);
        }
        int[] nums = new int[tCountMap.size()];
        int i = 0;
        Set<Map.Entry<Character, Integer>> entries = tCountMap.entrySet();
        for (Map.Entry<Character, Integer> entry : entries) {
            nums[i++] = entry.getValue();
        }
        Arrays.sort(nums);
        int len = nums.length;
        int res = (nums[len - 1] - 1) * (n + 1) + 1;
        for (int j = len - 2; j >= 0; j--) {
            if (nums[j] == nums[len - 1]) {
                res++;
            } else {
                break;
            }
        }
        return Math.max(res, tasks.length);
    }

//    给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
//
//    你找到的子数组应是最短的，请输出它的长度。
//
//    示例 1:
//
//    输入: [2, 6, 4, 8, 10, 9, 15]
//    输出: 5
//    解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

    public int findUnsortedSubarray(int[] nums) {
        int[] snums = nums.clone();
        Arrays.sort(snums);
        int start = snums.length, end = 0;
        for (int i = 0; i < snums.length; i++) {
            if (snums[i] != nums[i]) {
                start = Math.min(start, i);
                end = Math.max(end, i);
            }
        }
        return (end - start >= 0 ? end - start + 1 : 0);
    }

    public int findUnsortedSubarray2(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        int l = nums.length - 1, r = 0;
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
                Integer k = stack.pop();
                l = Math.min(l, k);
            }
            stack.push(i);
        }
        stack.clear();
        for (int i = nums.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
                Integer k = stack.pop();
                r = Math.max(r, k);
            }
            stack.push(i);
        }
        return r - l > 0 ? r - l + 1 : 0;
    }


    public int subarraySum(int[] nums, int k) {
        if (nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        if (nums[0] == k) {
            dp[0] = 1;
        }
        for (int i = 1; i < nums.length; i++) {
            dp[i] = dp[i - 1] + getCount(nums, i, k);
        }
        return dp[nums.length - 1];
    }

    private int getCount(int[] nums, int i, int k) {
        int sum = 0, res = 0;
        for (int j = i; j >= 0; j--) {
            sum += nums[j];
            if (sum == k) {
                res++;
            }
        }
        return res;
    }

    public int subarraySum2(int[] nums, int k) {
        int count = 0, sum = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (map.containsKey(sum - k))
                count += map.get(sum - k);
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }

    public int maxArea(int[] height) {
        int i = 0, j = height.length - 1;
        int res = 0;
        while (i < j) {
            if (height[i] < height[j]) {
                res = Math.max(res, (j - i) * height[i]);
                i++;
            } else {
                res = Math.max(res, (j - i) * height[j]);
                j--;
            }
        }
        return res;
    }


    public int[] productExceptSelf(int[] nums) {
        int[] left = new int[nums.length];
        int[] right = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            if (i > 0) {
                left[i] = left[i - 1] * nums[i - 1];
            } else {
                left[i] = 1;
            }
        }
        for (int i = nums.length - 1; i >= 0; i--) {
            if (i < nums.length - 1) {
                right[i] = right[i + 1] * nums[i + 1];
            } else {
                right[i] = 1;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            nums[i] = left[i] * right[i];
        }
        return nums;
    }

    public int[] decompressRLElist(int[] nums) {
        int n = 0;
        int len = nums.length;
        for (int i = 0; i <= len - 2; i += 2) {
            n += nums[i];
        }
        int[] res = new int[n];
        int k = 0;
        for (int i = 0; i <= len - 2; i += 2) {
            int m = nums[i];
            for (int j = 0; j < m; j++) {
                res[k++] = nums[i + 1];
            }
        }
        return res;
    }

    public int game(int[] guess, int[] answer) {
        int len = guess.length;
        int res = 0;
        for (int i = 0; i < len; i++) {
            if (guess[i] == answer[i]) {
                res++;
            }
        }
        return res;
    }

    public int findNumbers(int[] nums) {
        int res = 0;
        for (int num : nums) {
            boolean flg = String.valueOf(num).length() % 2 == 0;
            if (flg) res++;
        }
        return res;
    }

    public int numJewelsInStones(String J, String S) {
        char[] chars = J.toCharArray();
        HashSet<Character> characters = new HashSet<>();
        for (Character c : chars) {
            characters.add(c);
        }
        int res = 0;
        char[] chars1 = S.toCharArray();
        for (Character c : chars1) {
            if (characters.contains(c)) {
                res++;
            }
        }
        return res;
    }

    public int subtractProductAndSum(int n) {
        int sum = 0, mul = 1;
        while (n != 0) {
            int temp = n % 10;
            n /= 10;
            sum += temp;
            mul *= temp;
        }
        return mul - sum;
    }

    public int maxIncreaseKeepingSkyline(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[] marr = new int[m];
        int[] narr = new int[n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] > marr[i]) {
                    marr[i] = grid[i][j];
                }
                if (grid[i][j] > narr[j]) {
                    narr[j] = grid[i][j];
                }
            }
        }
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                res += Math.min(marr[i], narr[j]) - grid[i][j];
            }
        }

        return res;
    }

    public List<List<Integer>> groupThePeople(int[] groupSizes) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        List<List<Integer>> res = new LinkedList<>();
        for (int i = 0; i < groupSizes.length; i++) {
            List<Integer> list = map.get(groupSizes[i]);
            if (list == null) {
                ArrayList<Integer> value = new ArrayList<>();
                value.add(i);
                map.put(groupSizes[i], value);
                res.add(value);
            } else {
                if (list.size() == groupSizes[i]) {
                    map.remove(groupSizes[i]);
                    ArrayList<Integer> value = new ArrayList<>();
                    value.add(i);
                    map.put(groupSizes[i], value);
                    res.add(value);
                } else {
                    list.add(i);
                }
            }
        }
        return res;
    }

    public int[] deckRevealedIncreasing(int[] deck) {
        Arrays.sort(deck);
        int len = deck.length;
        if (len == 0) return deck;
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < len; i++) {
            queue.offer(i);
        }
        int[] res = new int[len];
        for (int d : deck) {
            Integer index = queue.poll();
            res[index] = d;
            if (!queue.isEmpty()) {
                queue.offer(queue.poll());
            }
        }
        return res;
    }

    public int[] countBits(int num) {
        int[] res = new int[num + 1];
        for (int i = 1; i <= num; i++) {
            res[i] = res[i >> 1] + i & 1;
        }
        return res;
    }

    public int matrixScore(int[][] A) {
        int m = A.length;
        if (m == 0) return 0;
        int n = A[0].length;
        int res = 0;
        for (int j = 1; j < n; j++) {
            int col = 0;
            for (int i = 0; i < m; i++) {
                if (A[i][0] == 0) {
                    col += ~A[i][j];
                } else {
                    col += A[i][j];
                }
            }
            res += Math.max(col, m - col) * (1 << (n - 1 - j));
        }
        res += m * (1 << (n - 1));
        return res;

    }

    public int matrixScore2(int[][] A) {
        int R = A.length, C = A[0].length;
        int ans = 0;
        for (int c = 0; c < C; ++c) {
            int col = 0;
            for (int r = 0; r < R; ++r)
                col += A[r][c] ^ A[r][0];
            ans += Math.max(col, R - col) * (1 << (C - 1 - c));
        }
        return ans;
    }

    public String removeDuplicates(String S) {
        char[] chars = S.toCharArray();
        int len = chars.length;
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < len; i++) {
            if (stack.isEmpty()) {
                stack.push(chars[i]);
                continue;
            }
            if (stack.peek() == chars[i]) {
                stack.pop();
            } else {
                stack.push(chars[i]);
            }
        }
        if (stack.isEmpty()) return "";
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }

    public static String defangIPaddr(String address) {
        String[] split = address.split("\\.");
        StringBuilder sb = new StringBuilder();
        int len = split.length;
        for (int i = 0; i < len - 1; i++) {
            sb.append(split[i]).append("[.]");
        }
        sb.append(split[len - 1]);
        return sb.toString();
    }

    public int maximum69Number(int num) {
        String numStr = Integer.toString(num);
        String s = numStr.replaceFirst("6", "9");
        return Integer.parseInt(s);
    }

    public int[] singleNumber(int[] nums) {
        Set<String> sets = new HashSet<>();
        for (int num : nums) {
            String numStr = String.valueOf(num);
            if (sets.contains(numStr)) {
                sets.remove(numStr);
            } else {
                sets.add(numStr);
            }
        }

        int[] res = new int[sets.size()];
        int i = 0;
        for (String numStr : sets) {
            res[i++] = Integer.valueOf(numStr);
        }
        return res;
    }

    public int[] singleNumber2(int[] nums) {
        int bitmask = 0;
        for (int num : nums) {
            bitmask ^= num;
        }
        int diff = bitmask & (-bitmask);
        int x = 0;
        for (int num : nums) {
            if ((num & diff) != 0) {
                x ^= num;
            }
        }
        return new int[]{x, bitmask ^ x};
    }

    public int singleNumber33(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
        for (Map.Entry<Integer, Integer> entry : entries) {
            if (entry.getValue() == 1) {
                return entry.getKey();
            }
        }
        return -1;
    }

    public int maxProfit(int[] prices) {
        int fstMineprice = Integer.MAX_VALUE, fstMaxprofit = 0;
        int secMinprice = Integer.MAX_VALUE, secMaxprofit = 0;
        for (int p : prices) {
            fstMineprice = Math.min(fstMineprice, p);
            fstMaxprofit = Math.max(fstMaxprofit, p - fstMineprice);
            secMinprice = Math.min(secMinprice, p - fstMaxprofit);
            secMaxprofit = Math.max(secMaxprofit, p - secMinprice);
        }
        return secMaxprofit;
    }
}
